package LeetCode;
//本题与主站 21 题相同
public class TestOffer25 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //递归方法
        //判断两个链表是否为空
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            // 此时要把list1.next和整个list2交给merge
            // 然后将结果拼接到list1.next
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // 此时要把list1和整个list2.next交给merge
            // 然后将结果拼接到list2.next
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
        //普通方法
//        //判断两个链表是否为空
//        if (list1==null){
//            return list2;
//        }
//        if (list2==null){
//            return list1;
//        }
//        //定义一个虚拟头节点来连接两个链表元素
//        ListNode dummyHead = new ListNode(101);
//        //定义last用来连接节点与虚拟头节点
//        ListNode last = dummyHead;
//        //当两个链表剩余元素都不为空时
//        while (list1!=null&&list2!=null){
//            //当list1的值小于list2的时让last指向list1,list1后移
//            if (list1.val<=list2.val){
//                last.next=list1;
//                last=list1;
//                list1=list1.next;
//            }else {
//                //当list2的值小于list1的时让last指向list2,list2后移
//                last.next=list2;
//                last=list2;
//                list2=list2.next;
//            }
//        }
//        //如果list1为空让last指向剩余的list2
//        if (list1==null){
//            last.next=list2;
//        }else {
//            //反之list2为空让last指向剩余的list1
//            last.next=list1;
//        }
//        return dummyHead.next;
    }
}
